package com.github.yangyishe.p200;

import com.github.yangyishe.TreeNode;

/**
 * 101. 对称二叉树
 * https://leetcode.cn/problems/symmetric-tree/?envType=study-plan-v2&envId=top-interview-150
 *
 * 给你一个二叉树的根节点 root ， 检查它是否轴对称。
 *
 *
 *
 * 示例 1：
 *
 *
 * 输入：root = [1,2,2,3,4,4,3]
 * 输出：true
 * 示例 2：
 *
 *
 * 输入：root = [1,2,2,null,3,null,3]
 * 输出：false
 *
 *
 * 提示：
 *
 * 树中节点数目在范围 [1, 1000] 内
 * -100 <= Node.val <= 100
 *
 *
 * 进阶：你可以运用递归和迭代两种方法解决这个问题吗？
 */
public class Problem101 {
    public static void main(String[] args) {
        Integer[] root=new Integer[]{1,2,2,null,3,null,3};
        TreeNode rootNode = TreeNode.getInstance(root);

        Problem101 problem101 = new Problem101();
        boolean symmetric = problem101.isSymmetric(rootNode);
        System.out.println(symmetric);
    }

    /**
     * 思路:
     * 仍然是遍历的变体.
     *
     * 譬如还是按照前序遍历的模板.
     * 分别对节点的左右树, 进行第一方向不同的遍历
     *
     * @param root
     * @return
     */
    public boolean isSymmetric(TreeNode root) {
        if(root==null){
            return true;
        }
        return preOrderCompare(root.left,root.right);
    }


    public boolean preOrderCompare(TreeNode leftTmp,TreeNode rightTmp){
        if(leftTmp==null&&rightTmp==null){
            return true;
        }
        if(leftTmp==null||rightTmp==null){
            return false;
        }
        if(leftTmp.val!=rightTmp.val){
            return false;
        }

        boolean b = preOrderCompare(leftTmp.left, rightTmp.right);
        if(!b){
            return false;
        }

        return preOrderCompare(leftTmp.right,rightTmp.left);

    }
}
